DROPS

Document

Diameter of Polyhedra: Limits of Abstraction

Authors: Friedrich Eisenbrand, Nicolai Hähnle, Alexander Razborov, and Thomas Rothvoß

Published in: Dagstuhl Seminar Proceedings, Volume 10211, Flexible Network Design (2010)

Abstract

We investigate the diameter of a natural abstraction of the $1$-skeleton of polyhedra. Even if this abstraction is more general than other abstractions previously studied in the literature, known upper bounds on the diameter of polyhedra continue to hold here. On the other hand, we show that this abstraction has its limits by providing an almost quadratic lower bound.

Cite as

Friedrich Eisenbrand, Nicolai Hähnle, Alexander Razborov, and Thomas Rothvoß. Diameter of Polyhedra: Limits of Abstraction. In Flexible Network Design. Dagstuhl Seminar Proceedings, Volume 10211, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{eisenbrand_et_al:DagSemProc.10211.2,
  author =	{Eisenbrand, Friedrich and H\"{a}hnle, Nicolai and Razborov, Alexander and Rothvo{\ss}, Thomas},
  title =	{{Diameter of Polyhedra: Limits of Abstraction}},
  booktitle =	{Flexible Network Design},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10211},
  editor =	{Anupam Gupta and Stefano Leonardi and Berthold V\"{o}cking and Roger Wattenhofer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10211.2},
  URN =		{urn:nbn:de:0030-drops-27247},
  doi =		{10.4230/DagSemProc.10211.2},
  annote =	{Keywords: Polyhedra, Graphs}
}

Document

DOI: 10.4230/DagSemProc.10071.10

Recent Hardness Results for Periodic Uni-processor Scheduling

Authors: Friedrich Eisenbrand and Thomas Rothvoss

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract

Consider a set of $n$ periodic tasks $ au_1,ldots, au_n$ where $ au_i$ is described by an execution time $c_i$, a (relative) deadline $d_i$ and a period $p_i$. We assume that jobs are released synchronously (i.e. at each multiple of $p_i$) and consider pre-emptive, uni-processor schedules. We show that computing the response time of a task $ au_n$ in a Rate-monotonic schedule i.e. computing [ minleft{ r geq mid c_n + sum_{i=1}^{n-1} leftlceil frac{r}{p_i} ight ceil c_i leq r ight} ] is (weakly) $mathbf{NP}$-hard (where $ au_n$ has the lowest priority and the deadlines are implicit, i.e. $d_i = p_i$). Furthermore we obtain that verifying EDF-schedulability, i.e. [ forall Q geq 0: sum_{i=1}^n left( leftlfloor frac{Q-d_i}{p_i} ight floor +1 ight)cdot c_i leq Q ] for constrained-deadline tasks ($d_i leq p_i$) is weakly $mathbf{coNP}$-hard.

Cite as

Friedrich Eisenbrand and Thomas Rothvoss. Recent Hardness Results for Periodic Uni-processor Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{eisenbrand_et_al:DagSemProc.10071.10,
  author =	{Eisenbrand, Friedrich and Rothvoss, Thomas},
  title =	{{Recent Hardness Results for Periodic Uni-processor Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.10},
  URN =		{urn:nbn:de:0030-drops-25458},
  doi =		{10.4230/DagSemProc.10071.10},
  annote =	{Keywords: Hardness, periodic scheduling, uni-processor scheduling}
}

Search Results

Documents authored by Rothvoss, Thomas

Diameter of Polyhedra: Limits of Abstraction

Abstract

Cite as

Recent Hardness Results for Periodic Uni-processor Scheduling

Abstract

Cite as

Thanks for your feedback!

Could not send message